package com.zjsru.leetcode75.level1.tree;

/**
 * @Author: cookLee
 * @Date: 2023-12-17
 * 二叉树的最近公共祖先
 */
public class LowestCommonAncestor {

    /**
     * 主
     * \
     * 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
     * 输出：3
     * 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
     * \
     * 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
     * 输出：5
     * 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身
     * \
     * @param args args
     */
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(3, new TreeNode(9, null, null), new TreeNode(20, new TreeNode(15, null, null), new TreeNode(7, null, null)));
        LowestCommonAncestor lowestCommonAncestor = new LowestCommonAncestor();
        TreeNode p = new TreeNode(5);
        TreeNode q = new TreeNode(4);
        System.out.println(lowestCommonAncestor.lowestCommonAncestor(tree, p, q));
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q){
            return root;
        }
        TreeNode leftTree = this.lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree = this.lowestCommonAncestor(root.right,p,q);
        //左子树为空，说明公共节点在右子树或者是右子树指向了公共节点
        if(leftTree == null){
            return rightTree;
        }
        //同理
        if(rightTree == null){
            return leftTree;
        }
        //如果左右子树都不为空，则说明当面root为公共节点
        return root;
    }
}
